HPI6: Target Practice // Advanced

Archer Arthur is practicing with his bow and arrows. He decides to challenge himself by shooting at N trees at various distances away. Skilled as he is, Arthur does not miss any shots, but he requires more time to aim and adjust his bow for farther trees than closer ones. Specifically, a tree that is D units away takes Arthur D seconds to aim and shoot at. Arthur also needs to take R additional seconds to reload after every shot (at the beginning, his bow is loaded with an arrow but not properly aimed). To make the challenge more interesting, Arthur assigns point values P_i to each of the trees. If Arthur gives himself S total seconds for the challenge, what is the maximum number of points he can attain?

1 <= N <= 1,000
1 <= S <= 10,000
0 <= R <= 1,000
1 <= D_i <= 25
1 <= P_i <= 1,000,000

Input Format

Line 1: Three space-separated integers N, S, and R: the total number of trees, the total time, and the reload time
Lines 2...N+1: Line i+1 contains two space-separated integers D_i and P_i, the distance and point value of tree i

Sample Input

4 10 2
1 9
7 2
3 4
5 6

Output Format

Line 1: The maximum number of points Arthur can attain

Sample Output

15